package binaryTree;

import normalArray.productExceptSelf;
import utils.binaryTreeUtil.TreeNode;

public class buildTree {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // pre负责找中间，in负责找左右
        TreeNode treeNode = build(preorder, 0, inorder, 0, inorder.length - 1);
        return treeNode;
    }

    public TreeNode build(int[] preOrder, int rpos, int[] inorder, int li, int ri) {
        if (li>ri||rpos>preOrder.length-1) {
            return null;
        }
        // 中间节点
        int index = 0;
        for (int i = li; i <= ri; i++) {
            if (inorder[i] == preOrder[rpos]) {
                index = i;
                break;
            }
        }
        // pre中的
        int firstL = 0, firstR = 0;
        firstL = rpos + 1;
        // 左节点的个数
        firstR = firstL + (index - li);
        TreeNode node = new TreeNode(preOrder[rpos]);
        TreeNode lNode = build(preOrder, firstL, inorder, li, index - 1);
        TreeNode rNode = build(preOrder, firstR, inorder, index + 1, ri);
        node.left = lNode;
        node.right = rNode;
        return node;

    }

    public static void main(String[] args) {

    }
}
